package org.example.code.test2024.nine_mouth;

public class test0918 {

    public boolean isInterleave(String s1, String s2, String s3) {
        int n=s1.length(),m=s2.length(),l=s3.length();
        if(n+m!=l){
            return false;
        }
        boolean[][] dp = new boolean[n+1][m+1];
        dp[0][0] = true;
        for(int i=1;i<=n;i++){
            dp[i][0]=dp[i-1][0]&&s1.charAt(i-1)==s3.charAt(i-1);
        }
        for(int i=1;i<=m;i++){
            dp[0][i]=dp[0][i-1]&&s2.charAt(i-1)==s3.charAt(i-1);
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(dp[i-1][j]&&s1.charAt(i-1)==s3.charAt(i+j-1)){
                    dp[i][j]=true;
                }else if(dp[i][j-1]&&s2.charAt(j-1)==s3.charAt(i+j-1)){
                    dp[i][j]=true;
                }
            }
        }
        return dp[n][m];
    }


    public int maxProfit(int[] prices) {
        int n = prices.length;
        if(n==0){
            return 0;
        }
        int[][][] dp = new int[n][3][2];
       for(int i=0;i<3;i++){
           dp[0][i][0]=0;
           dp[0][i][1]=-prices[0];
       }

       for(int i=1;i<n;i++){
           for(int j=1;j<3;j++){
               dp[i][j][0]=Math.max(dp[i-1][j][0],dp[i-1][j][1]+prices[i]);
               dp[i][j][1]=Math.max(dp[i-1][j][1],dp[i-1][j-1][0]-prices[i]);
           }
       }
       return dp[n-1][2][0];
    }

    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        if(n==0||k==0){
            return 0;
        }
        int[][][] dp = new int[n][k+1][2];
        for(int i=0;i<=k;i++){
            dp[0][i][0]=0;
            dp[0][i][1]=-prices[0];
        }

        for(int i=1;i<n;i++){
            for(int j=1;j<=k;j++){
                dp[i][j][0]=Math.max(dp[i-1][j][0],dp[i-1][j][1]+prices[i]);
                dp[i][j][1]=Math.max(dp[i-1][j][1],dp[i-1][j-1][0]-prices[i]);
            }
        }
        int max = Integer.MIN_VALUE;
        for(int i=0;i<=k;i++){
            max = Math.max(dp[n-1][i][0],max);
        }
        return max;
    }

    public int maximalSquare(char[][] matrix) {
        int n = matrix.length;
        if(n==0){
            return 0;
        }
        int m = matrix[0].length;
        int[][] dp = new int[n][m];
        int max = Integer.MIN_VALUE;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(matrix[i][j]=='1'){
                    if(i==0||j==0){
                        dp[i][j]=1;
                    }else{
                        dp[i][j]=Math.min(dp[i-1][j],Math.min(dp[i-1][j-1],dp[i][j-1]))+1;
                    }
                    max = Math.max(max,dp[i][j]);
                }
            }
        }
        return max*max;
    }


    public int reverseBits(int n) {
        int result = 0;
        for (int i = 0; i < 32; i++) {
            int lastBit = n & 1;
            result = (result << 1) | lastBit;
            n >>= 1;
            System.out.println(lastBit+" "+result+" "+n);
        }
        return result;
    }

    public int hammingWeight(int n) {
        int sum=0;
        for(int i=0;i<32;i++){
            if((n&1)==1){
                sum++;
            }
            n>>=1;
        }
        return sum;
    }

    public int singleNumber(int[] nums) {
        int one=0;
        int two=0;
        for(int num:nums){
            two=two|(one&num);
            one=one^num;
            int t=~(one&two);
            one=one&t;
            two=two&t;
        }
        return one;
    }

    public int rangeBitwiseAnd(int left, int right) {
        int sum = 0;
        while(left!=right){
            left=left>>1;
            right=right>>1;
            sum++;
        }
        return left<<sum;
    }


    public static void main(String[] args) {
        test0918 test = new test0918();
        System.out.println(test.rangeBitwiseAnd(5,7));
    }

}
